﻿#pragma once
#include <iostream>
using namespace std;

namespace key
{
	template<class K>
	struct BSTNode
	{
		K _key;
		BSTNode<K>* _left;
		BSTNode<K>* _right;
		BSTNode(const K& key)
			:_key(key)
			, _left(nullptr)
			, _right(nullptr)
		{
		}
	};
	template<class K>
	class BSTree
	{
		using Node = BSTNode<K>;
	public:
		bool Insert(const K& key)
		{
			//1.树为空，则直接新增结点，赋值给root指针
			if (_root == nullptr)
			{
				_root = new Node(key);
				return true;
			}
			//2. 树不空，按⼆叉搜索树性质，插⼊值⽐当前结点⼤往右⾛，插⼊值⽐当前结点⼩往左⾛，找到空位置，插⼊新结点。
			//3. 如果⽀持插⼊相等的值，插⼊值跟当前结点相等的值可以往右⾛，也可以往左⾛，找到空位置，插⼊新结点。
			//（要注意的是要保持逻辑⼀致性，插⼊相等的值不要⼀会往右⾛，⼀会往左⾛
			Node* parents = nullptr;
			Node* cur = _root;

			while (cur)
			{
				if (cur->_key > key)
				{
					parents = cur;
					cur = cur->_left;
				}
				else if (cur->_key < key)
				{
					parents = cur;
					cur = cur->_right;
				}
				else
				{
					cout << "不支持插入相同数字" << endl;
					return false;
				}
			}

			cur = new Node(key);

			if (parents->_key > key)
			{
				parents->_left = cur;
			}
			else
			{
				parents->_right = cur;
			}

			return true;
		}
		bool Find(const K& key)
		{
			Node cur = _root;
			while (cur)
			{
				if (cur->_key > key)
				{
					cur = cur->_left;
				}
				else if (cur->_key < key)
				{
					cur = cur->_right;
				}
				else
				{
					return true;
				}
			}
			return true;
		}
		bool Erase(const K& key)
		{
			Node* parents = nullptr;
			Node* cur = _root;

			while (cur)
			{
				if (cur->_key > key)
				{
					parents = cur;
					cur = cur->_left;
				}
				else if (cur->_key < key)
				{
					parents = cur;
					cur = cur->_right;
				}
				else
				{
					//由于二叉查找树的性质，如果将当前节点替换为左子树中最大的或者右子树中最小的一定不会破坏二叉查找树的结构
					/*如果查找元素存在则分以下四种情况分别处理：（假设要删除的结点为N）
					1. 要删除结点N左右孩⼦均为空
					2. 要删除的结点N左孩⼦位空，右孩⼦结点不为空
					3. 要删除的结点N右孩⼦位空，左孩⼦结点不为空
					4. 要删除的结点N左右孩⼦结点均不为空
					对应以上四种情况的解决⽅案：
					1. 把N结点的⽗亲对应孩⼦指针指向空，直接删除N结点（情况1可以当成2或者3处理，效果是⼀样的）
					2. 把N结点的⽗亲对应孩⼦指针指向N的右孩⼦，直接删除N结点
					3. 把N结点的⽗亲对应孩⼦指针指向N的左孩⼦，直接删除N结点
					4. ⽆法直接删除N结点，因为N的两个孩⼦⽆处安放，只能⽤替换法删除。找N左⼦树的值最⼤结点
					R(最右结点)或者N右⼦树的值最⼩结点R(最左结点)替代N，
					因为这两个结点中任意⼀个，放到N的位置，都满⾜⼆叉搜索树的规则。
					替代N的意思就是N和R的两个结点的值交换，转⽽变成删除R结点，R结点符合情况2或情况3，可以直接删除。*/
					if (cur->_left == nullptr)
					{
						if (cur == _root)//特判特殊情况
						{
							cur = cur->_right;
						}
						else
						{
							if (cur == parents->_left)
							{
								parents->_left = cur -> _right;
							}
							else
							{
								parents->_right = cur->_right;
							}
						}
						delete cur;
					}
					else if (cur->_right == __nullptr)
					{
						if (cur == _root)
						{
							cur = cur->_left;
						}
						else
						{
							if (cur == parents->_left)
							{
								parents->_left = cur->_left;
							}
							else
							{
								parents->_right = cur->_left;
							}
						}
						delete cur;
					}
					else
					{
						// 左右都不为空
						// 右子树最左节点

						Node* replaceParent = cur;
						Node* replaceCur = cur ->_right;
						while(replaceCur->_left)
						{
							replaceParent = replaceCur;
							replaceCur = replaceCur->_left;
						}
						cur->_key = replaceCur->_key;

						if (replaceParent->_left == replaceCur)
						{
							replaceParent->_left = replaceCur->_right;
						}
						else
						{
							replaceParent->_right = replaceCur->_right;
						}
					}
					return true;
				}
			}
			return false;
		}
		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}
	private:
		void _InOrder(Node* root)
		{
			if (root == nullptr) return;
			_InOrder(root->_left);
			cout << root->_key << ' ';
			_InOrder(root->_right);
		}
		Node* _root = nullptr;
	};
}